package jtg;

import soot.Unit;

import java.util.ArrayList;
import java.util.List;

public class PrimePath {
    public static List<List<Unit>> calSimplePath(DirectedGraph dg) {
        List<List<Unit>> simplePath = new ArrayList<>();
        for (Unit u : dg.vertex) {
            List<Unit> path = new ArrayList<>();
            dfs(u, dg, path, simplePath);
        }
        return simplePath;
    }

    public static void dfs(Unit u, DirectedGraph dg, List<Unit> path, List<List<Unit>> simplePath) {
        for (Unit t : path) {
            if (u.equals(t)) {
                List<Unit> tmp = new ArrayList<>(path);
                if (u.equals(path.get(0))) {
                    tmp.add(u);
                }
                path.add(u);
                simplePath.add(tmp);
                return;
            }
        }
        for (Unit t : dg.tail) {
            if (u.equals(t)) {
                path.add(u);
                List<Unit> tmp = new ArrayList<>(path);
                simplePath.add(tmp);
                return;
            }
        }
        path.add(u);
        for (int i = 0; i < dg.n; ++i) {
            if (dg.edge[dg.vertex.indexOf(u)][i]) {
                dfs(dg.vertex.get(i), dg, path, simplePath);
                path.remove(path.size() - 1);
            }
        }
    }

    public static List<List<Unit>> calPrimePath(List<List<Unit>> simplePath) {
        List<List<Unit>> primePath = new ArrayList<>(simplePath);
        for (List<Unit> l : simplePath) {
            for (List<Unit> m : simplePath) {
                if (!m.equals(l)) {
                    if (l.toString().substring(1, (l.toString()).length() - 1).contains(m.toString().substring(1, m.toString().length() - 1))) {
                        primePath.remove(m);
                    }
                }
            }
        }
//        for(List<Unit> l:simplePath){
//            System.out.println(l);
//        }
//        for(List<Unit> l:primePath){
//            System.out.println(l);
//        }
        return primePath;
    }

    public static List<List<Unit>> calCompletePath(List<List<Unit>> primePath, DirectedGraph dg) {
        List<List<Unit>> completePath = new ArrayList<>();
        for (List<Unit> p : primePath) {
            List<Unit> path = new ArrayList<>();
            List<Unit> ret = new ArrayList<>();
            List<Unit> ret2 = new ArrayList<>();
            boolean flag = false;

            DFS1(dg.vertex.get(0), p.get(0), dg, path, ret);
            for (Unit t : dg.tail) {
                boolean[] visited2 = new boolean[dg.n + 1];
                DFS2(p.get(p.size() - 1), t, dg, path, ret2, visited2);
            }
//            System.out.println("ret2"+ret2);
            for (Unit t : dg.tail) {
                if (p.get(p.size() - 1) == t) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                ret.addAll(p);
            } else {
                ret.addAll(p);
                boolean f = false;
                for (Unit t : dg.tail) {
                    for (Unit r : ret2) {
                        if (r.equals(t)) {
                            ret.addAll(ret2.subList(1, ret2.indexOf(r) + 1));
                            f = true;
                            break;
                        }
                    }
                    if (f)
                        break;
                }
            }
//            ret.addAll(p);
//            System.out.println("ret2:"+ret2);
//            ret.addAll(ret2.subList(1, ret2.size()));
            completePath.add(ret);
        }

        for (int i = 0; i < completePath.size() - 1; ++i)
            for (int j = i + 1; j < completePath.size(); ++j) {
                if (completePath.get(i).toString().substring(1, (completePath.get(i).toString()).length() - 1).contains(completePath.get(j).toString().substring(1, (completePath.get(j).toString()).length() - 1))) {
                    completePath.remove(j);
                }
            }
        return completePath;
    }

    public static void DFS1(Unit start, Unit end, DirectedGraph dg, List<Unit> path, List<Unit> ret) {
        if (start.equals(end)) {
            ret.addAll(path);
            return;
        }

        for (Unit t : dg.tail) {
            if (start.equals(t)) {
                path.add(start);
                return;
            }
        }
        path.add(start);

        for (int i = 0; i < dg.n; ++i) {
            if (dg.edge[dg.vertex.indexOf(start)][i]) {
                DFS1(dg.vertex.get(i), end, dg, path, ret);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void DFS2(Unit start, Unit end, DirectedGraph dg, List<Unit> path, List<Unit> ret, boolean[] visited) {

        path.add(start);
        visited[dg.vertex.indexOf(start)] = true;

        if (start.equals(end)) {
            ret.addAll(path);
            return;
        }
//        boolean flag=false;
        for (int i = 0; i < dg.n; ++i) {
            if (dg.edge[dg.vertex.indexOf(start)][i] && !visited[i]) {
//                flag=true;
                if (dg.vertex.get(i).equals(end)) {
                    path.add(dg.vertex.get(i));
                    ret.addAll(path);
                    return;
                } else {
                    DFS2(dg.vertex.get(i), end, dg, path, ret, visited);
                    path.remove(path.size() - 1);
                }
            }
        }
//        if(!flag){
//            path.remove(path.size()-1);
//        }
    }

    public static List<String> toNumber(List<List<Unit>> path, DirectedGraph dg) {
        List<String> ret = new ArrayList<>();
        for (List<Unit> p : path) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < p.size(); i++) {
                stringBuilder.append(dg.vertex.indexOf(p.get(i)) + 1);
                if (i != p.size() - 1) {
                    stringBuilder.append("->");
                }
            }
            ret.add(stringBuilder.toString());
        }
        return ret;
    }
}
